
/*
 * 
 * Invert Binary Tree 

Invert a binary tree.

     4
   /   \
  2     7
 / \   / \
1   3 6   9
to
     4
   /   \
  7     2
 / \   / \
9   6 3   1
Trivia:
This problem was inspired by this original tweet by Max Howell:
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

 * 
 * 思路：
 *   分治即可
 */
package com.leetcode.weicl.problems.no226;


/**
 * The Class Solution.<br>
 * 
 * @author FNST)WeiCL
 * @version 1.0
 */
public class Solution {
	
	
	void revert(TreeNode node) {
		if (node == null) {
			return;
		}
		TreeNode tmp = node.left;
		node.left = node.right;
		node.right = tmp;
		
		revert(node.left);
		revert(node.right);
	}
	
    public TreeNode invertTree(TreeNode root) {
    	revert(root);
    	
        return root;
    }
    
    public static void main(String[] args) {
	    Solution s = new Solution();
	    TreeNode root = new TreeNode(4);
	    root.left = new TreeNode(2);
	    root.left.left = new TreeNode(1);
	    root.left.right = new TreeNode(3);
	    root.right = new TreeNode(7);
	    root.right.left = new TreeNode(6);
	    root.right.right = new TreeNode(9);
	    
	    TreeNode rt = s.invertTree(root);
	    System.out.println(rt);
    }
}
